package com.leo.offer;

/**
 * 先序遍历和中序遍历重建二叉树
 * @author xuexiaolei
 * @version 2018年03月01日
 */
public class T06RebuildTree {
    private TreeNode buildTreeHelper(int[] inorder,int is,int ie,int[] preorder,int ps) {
        if(is>ie || ps >= preorder.length) {return null;}
        //首先从inorder中确定第一个，然后既可以划分左右子树
        TreeNode root = new TreeNode(preorder[ps]);
        int rootAtIn = is;
        while(inorder[rootAtIn] != (int)root.val) {rootAtIn ++;} //查找本节点的位置
        //拆分成两个子问题
        root.left =  buildTreeHelper(inorder,is,rootAtIn - 1,preorder,ps+1);
        root.right = buildTreeHelper(inorder,rootAtIn+1,ie,preorder,ps+rootAtIn - is + 1);
        return root;
    }
    public TreeNode buildTree(int[] inorder, int[] preorder) {//先序+中序恢复二叉树
        return buildTreeHelper(inorder,0,inorder.length-1,preorder,0);

    }


}
